package algorithm.tree;

import lombok.Data;

import java.util.LinkedList;
import java.util.List;

public class BST<K extends Comparable<K>, V> {
    @Data
    private class Node<K extends Comparable<K>, V> {
        //左节点
        private Node leftNode;
        //右节点
        private Node rightNode;
        //key
        private K key;
        //value
        private V value;

        private Node(K k, V v) {
            this.key = k;
            this.value = v;
        }
    }

    private Node<K, V> root;

    private int count;

    public boolean isEmpty() {
        return count == 0;
    }

    public int getCount() {
        return count;
    }

    public void insert(K key, V value) {
        root = insert(root, key, value);
    }

    public void insertRecursion(K key, V value) {
        root = insertRecursion(root, key, value);
    }

    public boolean contain(K k) {
        Node node = root;
        while (node != null) {
            if (node.key.compareTo(k) == 0) {
                return true;
            } else if (node.key.compareTo(k) < 0) {
                node = node.leftNode;
            } else {
                node = node.rightNode;
            }
        }
        return false;
    }

    public V search(K k) {
        Node<K, V> node = root;
        while (node != null) {
            if (node.key.compareTo(k) == 0) {
                return node.value;
            } else if (node.key.compareTo(k) < 0) {
                node = node.leftNode;
            } else {
                node = node.rightNode;
            }
        }
        return null;
    }

    private Node<K, V> insertRecursion(Node<K, V> node, K k, V v) {

        if (node == null) {
            count++;
            return new Node(k, v);
        }
        if (node.getKey().compareTo(k) == 0) {
            node.setValue(v);
        } else if (node.getKey().compareTo(k) > 0) {
            node.leftNode = insertRecursion(node.leftNode, k, v);
        } else {
            node.rightNode = insertRecursion(node.rightNode, k, v);
        }
        return node;
    }

    public Node<K, V> insert(Node<K, V> node, K k, V v) {
        if (node == null) {
            count++;
            node = new Node<>(k, v);
            return node;
        } else {
            Node<K, V> backup = node;
            while (true) {
                if (node.getKey().compareTo(k) == 0) {
                    node.setValue(v);
                    break;
                }
                if (node.getKey().compareTo(k) > 0) {
                    if (node.leftNode == null) {
                        count++;
                        node.leftNode = new Node<>(k, v);
                        break;
                    } else {
                        node = node.leftNode;
                    }
                } else {
                    if (node.rightNode == null) {
                        count++;
                        node.rightNode = new Node<>(k, v);
                        break;
                    } else {
                        node = node.rightNode;
                    }
                }
            }
            return backup;
        }
    }

    public void preOrder() {
        preOrder(root);
    }

    //前序遍历
    private void preOrder(Node<K, V> node) {
        if (node != null) {
            System.out.println("前序：" + node.value);
            preOrder(node.leftNode);
            //中序
            preOrder(node.rightNode);
            //后序
        }
    }

    public void inOrder() {
        inOrder(root);
    }

    //中序遍历
    private void inOrder(Node<K, V> node) {
        if (node != null) {
            inOrder(node.leftNode);
            System.out.println("中序：" + node.value);
            inOrder(node.rightNode);
        }
    }

    public void postOrder() {
        postOrder(root);
    }

    //后序遍历
    private void postOrder(Node<K, V> node) {
        if (node != null) {
            postOrder(node.leftNode);
            postOrder(node.rightNode);
            System.out.println("后序：" + node.value);
        }
    }

    public void levelOrder() {
        LinkedList<Node<K, V>> list = new LinkedList<>();
        list.add(root);
        while (!list.isEmpty()) {
            Node<K, V> kvNode = list.removeFirst();
            System.out.println("深度：" + kvNode.value);
            if (kvNode.leftNode != null) {
                list.add(kvNode.leftNode);
            }
            if (kvNode.rightNode != null) {
                list.add(kvNode.rightNode);
            }
        }
    }

    public Node<K, V> minimun() {
        return minimun(root);
    }

    private Node<K, V> minimun(Node<K, V> node) {
        if (node.leftNode == null) {
            return node;
        }
        return minimun(node);
    }

    public Node<K, V> maximun() {
        return maximun(root);
    }


    private Node<K, V> maximun(Node<K, V> node) {
        if (node.rightNode == null) {
            return node;
        }
        return maximun(node);
    }

    public void deleteMinNode() {
        deleteMinNode(root);
    }

    private Node<K, V> deleteMinNode(Node<K, V> node) {
        if (node.leftNode == null) {
            count--;
            return node.rightNode;
        }
        node.leftNode = deleteMinNode(node.leftNode);
        return node;
    }

    public void deleteMaxNode() {
        deleteMaxNode(root);
    }

    private Node<K, V> deleteMaxNode(Node<K, V> node) {
        if (node.rightNode == null) {
            count--;
            return node.leftNode;
        }
        node.rightNode = deleteMinNode(node.rightNode);
        return node;
    }

    public void remove(K k) {
        remove(root, k);
    }

    private Node<K, V> remove(Node<K, V> node, K k) {

        if (node == null) {
            return null;
        }
        if (node.getKey().compareTo(k) < 0) {
            node.rightNode = remove(node.getRightNode(), k);
            return node;
        }else if (node.getKey().compareTo(k) > 0 ){
            node.leftNode = remove(node.rightNode,k);
            return node;
        }else{
            if (node.leftNode==null){
                count--;
                return node.rightNode;
            }
            if (node.rightNode==null){
                count--;
                return node.leftNode;
            }
            Node<K,V> successor = minimun(node);
            Node<K, V> kvNode = deleteMinNode(node);
            successor.rightNode = kvNode;
            successor.leftNode = node.leftNode;
            return successor;
        }
    }


}
